package com.gaogzhen.datastructure.graph.undirected;

import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Graph;

import java.util.Iterator;

/**
 * 单点连通性
 * @author: Administrator
 * @createTime: 2023/03/03 19:58
 */
public class DepthFirstSearch {
    /**
     * 顶点是否标记
     */
    private boolean[] marked;

    /**
     * 与指定顶点连通的顶点总数
     */
    private int count;

    /**
     * 图
    */
    private Graph graph;

    /**
     * 起点
     */
    private int s;

    public DepthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        check(s);
        marked = new boolean[graph.V()];
        long start = System.currentTimeMillis();
        // dfs();
        dfsDel();
        long end = System.currentTimeMillis();
        System.out.println("用时：" + (end - start) + "ms");
    }

    /**
     * 搜索图g中与起点v连通的所有顶点
     */
    private void dfs() {
        // 栈记录搜索路径
        Stack<Iterator<Integer>> path = new Stack<>();
        // marked[v] = true;
        if (!marked[s]) {
            // 起点未标记，标记计数加1
            // 起点默认没标记，可以不加是否标记判断
            marked[s] = true;
            count++;
            Iterable<Integer> iterable = graph.adj(s);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                // 顶点对应的邻接表迭代器存入栈
                path.push(it);
            }
        }
        while (!path.isEmpty()) {
            Iterator<Integer> it = path.pop();
            int x;
            while (it.hasNext()) {
                // 邻接表迭代器有元素，获取元素
                x = it.next();
                if (!marked[x]) {
                    // 顶点未被标记，标记计数+1
                    marked[x] = true;
                    count++;
                    if (it.hasNext()) {
                        // 邻接表迭代器有元素重新入栈
                        path.push(it);
                    }
                    // 深度优先原则，当前迭代器入栈，新标记顶点的邻接表迭代器入栈，下次循环优先访问
                    Iterable<Integer> iterable = graph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        path.push(it);
                    }
                    break;
                }
            }

        }
    }

    private void  dfsDel() {
        // 支持后入先出和任意删除
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        stack.push(s);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (!marked[v]) {
                marked[v] = true;
                count++;
                for (int w : graph.adj(v)) {
                    // 访问同层顶点
                    if (!marked[w]) {
                        // 没被标记过顶点，入栈
                        if (stack.contains(w)) {
                            // 没被标记，但是已经入栈，说明之前是同层压入，需要移除重新压入
                            // 这样符合深度优先原则
                            stack.removeElement(w);
                        }
                        stack.push(w);
                    }
                }
            }
            else {
                // 顶点v的邻接顶点都已访问完毕，弹出顶点v，回溯
                stack.pop();
            }
        }
    }

    /**
     * 检测索引是否在范围之内
     * @param i 给定索引
     */
    private void check(int i) {
        if (i < 0 || i > graph.V() - 1) {
            throw new IndexOutOfBoundsException("索引越界异常");
        }
    }

    /**
     * 判断起点是否与给定顶点x连通
     * @param x 给定顶点
     * @return
     */
    public boolean marked(int x) {
        check(x);
        return marked[x];
    }

    /**
     * 返回图中与顶点想连通的顶点数
     * @return
     */
    public int count() {
        return count;
    }

}
